Fast Kalman Filter using Hierarchical-matrices and low-rank perturbative approach

摘要

We develop a fast algorithm for Kalman Filter applied to the random walkforecast model. The key idea is an efficient representation of the estimatecovariance matrix at each time-step as a weighted sum of two contributions -the process noise covariance matrix and a low rank term computed from ageneralized eigenvalue problem, which combines information from the noisecovariance matrix and the data. We describe an efficient algorithm to updatethe weights of the above terms and the computation of eigenmodes of thegeneralized eigenvalue problem (GEP). The resulting algorithm for the Kalmanfilter with a random walk forecast model scales as $\bigO(N)$ in memory and$\bigO(N \log N)$ in computational cost, where $N$ is the number of gridpoints. We show how to efficiently compute measures of uncertainty andconditional realizations from the state distribution at each time step. Anextension to the case with nonlinear measurement operators is also discussed.Numerical experiments demonstrate the performance of our algorithms, which areapplied to a synthetic example from monitoring CO$_2$ in the subsurface usingtravel time tomography.